package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class code1382 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static void main(String[] args) {
        Integer[] arrayA = new Integer[]{5,4,6,null,null,3,7};
        TreeNode root = buildtree(arrayA);

    }

    public static TreeNode buildtree(Integer[] arrayA){
        if (arrayA==null||arrayA.length==0)
            return null;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(arrayA[0]);
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()&&i<arrayA.length){
            TreeNode currentNode = queue.poll();
            if(i<arrayA.length && arrayA[i]!=null){
                currentNode.left = new TreeNode(arrayA[i]);
                queue.offer(currentNode.left);

            }
            i++;
            if (i < arrayA.length && arrayA[i] != null){
                currentNode.right = new TreeNode(arrayA[i]);
                queue.offer(currentNode.right);

            }
            i++;
        }
        return root;
    }


    public TreeNode balanceBST(TreeNode root) {
        //先将转为有序数组
        travesal(root);
        return getTree(res,0,res.size()-1);
    }

    private TreeNode getTree(ArrayList <Integer> nums, int left, int right) {
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums.get(mid));
        root.left = getTree(nums, left, mid - 1);
        root.right = getTree(nums, mid + 1, right);
        return root;
    }

    ArrayList<Integer> res = new ArrayList<>();
    private void travesal(TreeNode root) {
        if (root==null)
            return;
        travesal(root.left);
        res.add(root.val);
        travesal(root.right);
    }
}
